package top100;

import java.util.ArrayList;
import java.util.List;

/**
 * 448. 找到所有数组中消失的数字
 *
 * @see <a href="https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/description/">find-all-numbers-disappeared-in-an-array</a>
 */
public class _0448_findDisappearedNumbers {
    public static void main(String[] args) {

    }

    /**
     * 原地修改
     *
     * 由于 nums 的数字范围均在 [1,n] 中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义。
     *
     * 具体来说，遍历 nums 每遇到一个数 x，就让 nums[x−1] 增加 n。
     * 由于 nums 中所有数均在 [1,n] 中，增加以后，这些数必然大于 nnn。
     * 最后我们遍历 nums，若 nums[i] 未大于 nnn，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字。
     *
     * 注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对 n 取模来还原出它本来的值。
     *
     * 时间复杂度：O(n)。其中 n 是数组 nums 的长度。
     * 空间复杂度：O(1)。返回值不计入空间复杂度。
     *
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int num : nums) {
            // 得到num值对应的下标. 由于相同的值对应的下标相同，会重复累加，仅此取模，得到原值的数值
            int idx = (num - 1) % n;
            // num-1下标位置的数 +n放入nums数组中
            nums[idx] += n;
        }

        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i<n; i++) {
            if (nums[i] <= n) {
                // 证明这个位置从来没有被计算和累加过
                // 下标i从0开始, 但值从1，所以用i+1
                list.add(i + 1);  //i位置上的值i+1未曾出现过
            }
        }

        return list;
    }
}
